/**
 * 
 */
package array.passed2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class SpiralMatrix {

	/**
	Spiral Matrix
	
	Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

	For example,
	Given the following matrix:

	[
	[ 1, 2, 3 ],
	[ 4, 5, 6 ],
	[ 7, 8, 9 ]
	]

	You should return [1,2,3,6,9,8,7,4,5].
	 */
	public List<Integer> spiralOrderR(int[][] matrix) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		if (matrix != null && matrix.length > 0)
			spiralOrderRHelper(matrix, matrix.length, matrix[0].length, 0, result);
		return result;
	}

	public void spiralOrderRHelper(int[][] matrix, int rows, int cols, int level,
			ArrayList<Integer> result) {
		if (rows <= 0 || cols <= 0) {
			return;
		}

		if (rows == 1) {
			for (int i = 0; i < cols; i++) {
				result.add(matrix[level][level + i]);
			}
			return;
		}
		if (cols == 1) {
			for (int i = 0; i < rows; i++) {
				result.add(matrix[level + i][level]);
			}
			return;
		}
		// top 
		for (int i = 0; i < cols - 1; i++)
			result.add(matrix[level][level + i]);
		// right
		for (int i = 0; i < rows - 1; i++)
			result.add(matrix[level + i][level + cols - 1]);
		//bottom
		for (int i = cols - 1; i > 0; i--)
			result.add(matrix[level + rows - 1][level + i]);
		// left
		for (int i = rows - 1; i > 0; i--)
			result.add(matrix[level + i][level]);

		spiralOrderRHelper(matrix, rows - 2, cols - 2, level + 1, result);
	}

	 public List<Integer> spiralOrderI(int[][] matrix) {
	        List<Integer> result = new ArrayList<>();
	        if (matrix == null || matrix.length == 0)
	            return result;
	        
	        int rows = matrix.length;
	        int cols = matrix[0].length;
	        int level = 0;
	        
	        while (rows > 0 && cols > 0) {
	            if (rows == 1) {
	                for (int row = level, col = level; col <= level + cols - 1; col++) {
	                    result.add(matrix[row][col]);
	                }
	                break;
	            }
	            if (cols == 1) {
	                for (int row = level, col = level; row <= level + rows - 1; row++) {
	                    result.add(matrix[row][col]);
	                }
	                break;
	            }
	            
	            //top
	            for (int row = level, col = level; col < level + cols - 1; col++) {
	                result.add(matrix[row][col]);
	            }
	            // right
	            for (int row = level, col = level + cols - 1; row < level + rows - 1; row++) {
	                result.add(matrix[row][col]);
	            }
	            //bottom
	            for (int row = level + rows - 1, col = level + cols - 1; col > level; col --) {
	                result.add(matrix[row][col]);;
	            }
	            //left
	            for (int row = level + rows - 1, col = level; row > level; row--) {
	                result.add(matrix[row][col]);;
	            }
	            
	            level++;
	            rows -= 2;
	            cols -= 2;
	        }
	        
	        return result;
	    }
	
	/**
	Mar 28 '12897 / 2147

	Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

	For example,
	Given n = 3,
	You should return the following matrix:

	[
	[ 1, 2, 3 ],
	[ 8, 9, 4 ],
	[ 7, 6, 5 ]
	]
	 */
	public int[][] generateMatrix2R(int n) {
		int[][] matrix = new int[n][n];
		generateMatrix2RHelp(matrix, n, 1, 0);
		return matrix;
	}

	private void generateMatrix2RHelp(int[][] matrix, int length, int value, int level) {
		if (length <= 0)
			return;

		if (length == 1) {
			matrix[level][level] = value;
			return;
		}

		// top
		for (int i = 0; i < length - 1; i++)
			matrix[level][level + i] = value++;

		// right
		for (int i = 0; i < length - 1; i++)
			matrix[level + i][level + length - 1] = value++;

		//bottom
		for (int i = length - 1; i > 0; i--)
			matrix[level + length - 1][level + i] = value++;

		//left
		for (int i = length - 1; i > 0; i--)
			matrix[level + i][level] = value++;

		generateMatrix2RHelp(matrix, length - 2, value, level + 1);

	}	
	
    public int[][] generateMatrix2I(int n) {
        int[][] matrix = new int[n][n];
        if (n <= 0)
            return matrix;
       
        int length = matrix.length;
        int level = 0;
        int value = 1;
        while (length > 0) {
            if (length == 1) {
                matrix[level][level] = value;
                break;
            }
            
            // top
            for (int row = level, col = level; col < level + length - 1; col++) {
                matrix[row][col] = value++;
            }
            // right
            for (int row = level, col = level + length - 1; row < level + length - 1; row++) {
                matrix[row][col] = value++;   
            }
            //bottom
            for (int row = level + length - 1, col = level + length - 1; col > level; col--) {
               matrix[row][col] = value++; 
            }
            // left
            for (int row = level + length - 1, col = level; row >= level + 1; row--) {
                matrix[row][col] = value++;    
            }
            
            level++;
            length -= 2;
        }
        
        return matrix;
    }
	/**
	 * 
	 */
	public SpiralMatrix() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SpiralMatrix sm = new SpiralMatrix();
		int[][] matrix = new int[0][0];
		sm.spiralOrderI(matrix);

	}

}
